//
// Created by wormtql on 2020/11/24.
//

#include <map>
#include <string>
#include <cstring>
#include <fstream>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <set>
#include <cmath>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

struct Edge {
    int to;
    int from;
    int next;
};

// 图
#ifdef REMOTE
Edge edges[5000000];
int edge_count = 0;
int head[600000];
int node_count = 0;
int dis[600000];
int vis[600000];
int parent[600000];
#else
Edge edges[2000000];
int edge_count = 0;
int head[500000];
int node_count = 0;
int dis[500000];
int vis[500000];
int parent[500000];
#endif
map<string, int> name2id;
map<int, string> id2name;


// blacklist
set<int> blacklist;


// trace
int trace_count = 0;
vector<string> traces[6000];


void load_blacklist(char * filename) {
    ifstream file(filename);

    char c;
    char buf[1000] = { 0 };
    int l = 0;

    while (file >> c) {
        if (c != ',') {
            buf[l++] = c;
        } else {
            buf[l] = 0;
            l = 0;
            string temp(buf);
//            cout << temp << endl;
            if (name2id.find(temp) != name2id.end()) {
                blacklist.insert(name2id[temp]);
            }
        }
    }

    if (l != 0) {
        buf[l] = 0;
        string temp(buf);
        blacklist.insert(name2id[temp]);
    }
}

bool parseLine(const char * line, char * from, char * to) {
    int i = 0;
    bool flag = false;
    bool isFrom = true;

    int a = 0;
    int b = 0;

    while (line[i] != '\0') {
        if (line[i] == '\"') {
            if (!flag) {
                flag = true;
            } else {
                if (!isFrom) {
                    break;
                }
                flag = false;
                isFrom = false;
            }
            i++;
            continue;
        }

        if (flag) {
            if (isFrom) {
                from[a] = line[i];
                a++;
            } else {
                to[b] = line[i];
                b++;
            }
        }
        i++;
    }

    if (a == 0 || b == 0) {
        return false;
    }

    from[a] = 0;
    to[b] = 0;

    return true;
}

void parse_csv_line(char * line, vector<string> & data) {
    int state = 0;
    char buf[1000] = { 0 };
    int l = 0;

    int i = 0;
    while (line[i]) {
        if (state == 0) {
            if (line[i] == ',') {
                state = 1;
            } else {
                buf[l++] = line[i];
                i++;
            }
        } else if (state == 1) {
            buf[l] = 0;
            l = 0;
            data.push_back(string(buf));
            i++;
            state = 0;
        }
    }
    if (l != 0) {
        buf[l] = 0;
        data.emplace_back(buf);
    }
}

int register_node(char * name) {
    string temp(name);
    if (name2id.find(temp) == name2id.end()) {
        name2id[name] = node_count;
        id2name[node_count] = name;
        node_count++;
        return node_count - 1;
    } else {
        return name2id[temp];
    }
}

void add(int from, int to) {
    edges[edge_count].from = from;
    edges[edge_count].to = to;
    edges[edge_count].next = head[from];
    head[from] = edge_count;
    edge_count++;
}

//bool check(char * str) {
//    if (black_list.find(string(str)) == black_list.end()) {
//        return true;
//    }
//
//    return false;
//}

bool load_graph(char * filename) {
    ifstream file(filename);

    if (!file.is_open()) {
        return false;
    }

    char line[1000] = { 0 };
    while(file.getline(line, 1000)) {
        char from[100] = { 0 };
        char to[100] = { 0 };

        bool ret = parseLine(line, from, to);
        if (!ret) {
            printf("aaa\n");
            continue;
        }
//        if (!check(from) || !check(to)) {
//            continue;
//        }

        int from_id = register_node(from);
        int to_id = register_node(to);
        add(from_id, to_id);
//        add(to_id, from_id);
    }

    return true;
}

bool load_traces(char * filename, int limit) {
    ifstream file(filename);
    if (!file.is_open()) {
        return false;
    }

    char buf[10000];
    while(file.getline(buf, 10000) && trace_count < limit) {
//        char version[100];
//        char commit_id[100];
        vector<string> ts;
//        parse_trace_line(buf, version, commit_id, ts);
        parse_csv_line(buf, ts);

        for (const string & s: ts) {
//            printf("%s\n", s.c_str());
//            if (name2id.find(s) != name2id.end()) {
                traces[trace_count].push_back(s);
//            }
        }

        trace_count++;
    }

    return true;
}

void sp_single(int a) {
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(parent, -1, sizeof(parent));

    for (auto i = blacklist.begin(); i != blacklist.end(); i++) {
        vis[*i] = 1;
    }

    queue<int> q;
    q.push(a);
    dis[a] = 0;
    vis[a] = 1;

    while(!q.empty()) {
        int p = q.front();
        q.pop();

        for (int e = head[p]; e != -1; e = edges[e].next) {
            int to = edges[e].to;

            if (!vis[to]) {
                q.push(to);
                vis[to] = 1;
                dis[to] = dis[p] + 1;
                parent[to] = p;
            }
        }
    }
}

void init() {
    memset(edges, -1, sizeof(edges));
    memset(head, -1, sizeof(head));
    edge_count = 0;
    node_count = 0;
    name2id.clear();
}

int main(int argc, char * argv[]) {
#ifdef REMOTE
    printf("running remotely\n");
#endif
    if (argc < 6) {
        printf("calculate distance between every 2 node and cache them\n\n");
        printf("app <graph.dot> <trace.csv> <blacklist.txt> <output.csv> <function_list.txt>\n\n");
        printf("graph.dot:          call graph\n");
        printf("trace.csv:          call trace\n");
        printf("blacklist.txt:      black list\n");
        printf("output.csv:         distance matrix\n");
        printf("function_list.txt:  map function name to matrix index\n");
        return 0;
    }

    init();


    // load graph
    bool ret = load_graph(argv[1]);
    if (!ret) {
        printf("unable to open file \"%s\"\n", argv[1]);
    }
    printf("graph loaded\n");
    printf("node count: %d\n", node_count);
    printf("edge count: %d\n\n", edge_count);


    // load trace
    load_traces(argv[2], 10000);
    printf("traces loaded\n");
    printf("trace count: %d\n\n", trace_count);


    // load black list
    load_blacklist(argv[3]);
    printf("black list loaded\n");
    printf("omit function count: %d\n", blacklist.size());
    printf("sample: %s\n\n", id2name[*blacklist.begin()].c_str());

//    if (name2id.find("SYSC_wait4") == name2id.end()) {
//        printf("cannot find\n");
//    } else {
//        printf("worm\n");
//    }

    set<string> all_functions;
    vector<string> function_list_vec;
    for (int i = 0; i < trace_count; i++) {
        for (int j = 0; j < traces[i].size(); j++) {
            all_functions.insert(traces[i][j]);
        }
    }
    for (auto i = all_functions.begin(); i != all_functions.end(); i++) {
        function_list_vec.push_back(*i);
    }

    ofstream function_list(argv[5]);
    ofstream output(argv[4]);

    int count = function_list_vec.size();
    printf("all function count: %d\n", count);
    for (auto i = 0; i < count; i++) {
        function_list << function_list_vec[i] << endl;
    }

    for (int i = 0; i < count; i++) {
        if (name2id.find(function_list_vec[i]) == name2id.end()) {
            for (int j = 0; j < count; j++) {
                output << INF;
                if (j != count - 1) {
                    output << ",";
                }
            }
            output << endl;
        } else {
            sp_single(name2id[function_list_vec[i]]);
//            printf("aaa\n");
            for (int j = 0; j < count; j++) {
                if (
                    name2id.find(function_list_vec[j]) == name2id.end()
                    || blacklist.find(name2id[function_list_vec[i]]) != blacklist.end()
                    || blacklist.find(name2id[function_list_vec[j]]) != blacklist.end()
                ) {
                    output << INF;
                } else {
                    if (dis[name2id[function_list_vec[j]]] == 0 && i != j) {
//                        printf("%s %s\n", function_list_vec[i].c_str(), function_list_vec[j].c_str());
//                        printf("%d\n", name2id[function_list_vec[i]]);
                    }
                    output << dis[name2id[function_list_vec[j]]];
                }
                if (j != count - 1) {
                    output << ",";
                }
            }
            output << endl;
        }
        printf("%.6lf%%\n", (i + 1.0) / count * 100);
    }

    function_list.close();
    output.close();
}